const INF = Number.MAX_SAFE_INTEGER; // int范围内的最大值
/**
 * 普里姆(Prim)算法核心是贪心算法，加权无向连通图，求出它的最小生成树
 * prim算法跟dijkstra算法非常相似，最主要的区别就是prim无需加上回溯点的代价再去比较。
 * @param graph 图的邻接矩阵形式（顶点和顶点之间的关系，值是权值）
 */
export const prim = (graph: number[][]) => {
    const cost: number[] = []; // 每个顶点现存的最小代价
    const visited: boolean[] = []; // 保存每个顶点的处理状态
    const parent: number[] = []; // 回溯顶点的下标
    const length: number = graph.length; // 图中顶点的个数

    // 初始化cost和visited和parent
    for (let i = 0; i < length; i ++) {
        cost[i] = INF;
        visited[i] = false;
        parent[i] = -1;
    }

    // 因为每个顶点都要在最小生成树中，那么源顶点可以随意找一个，代价是0
    cost[0] = 0;

    // 遍历顶点，length减是因为源顶点代价已经知道了，算出其他顶点的最小代价即可
    for (let i = 0; i < length - 1; i ++) {
        // 选出列表中代价（权值）最小的顶点，贪心点1。
        const u = minCost(cost, visited);
        // 查看它的可访问邻接顶点，算出它邻接顶点与它连接的代价
        for (let v = 0; v < length; v ++) {
            /*
                邻接顶点要可访问，如果v与u相连的代价小于目前它存储的代价，
                那更新现存代价（有最小就存最小），贪心点2。
                prim跟dijkstra的区别：prim无需加上回溯点的代价再去比较
                也就是最小生成树的最小代价和最短路径的区别
            */
            if (!visited[v] && graph[u][v] !== 0 && graph[u][v] < cost[v]) {
                // 更新现存最小代价
                cost[v] = graph[u][v];
                // 更新回溯点
                parent[v] = u;
            }
        }
        // u的邻接顶点都遍历了，后面不会再来处理u了
        visited[u] = true;
    }
    return { cost, parent };
};
/**
 * 找出列表中距离源顶点最近的顶点(要是可访问)
 * @param cost 每个顶点距离源顶点的最小值
 * @param visited 每个顶点的访问状态
 */
const minCost = (cost: number[], visited: boolean[]) => {
    let minIndex = -1;
    let min = INF;
    for (let i = 0; i < cost.length; i ++) {
        // 可访问并且有更小的
        if (!visited[i] && cost[i] < min) {
            min = cost[i];
            minIndex = i;
        }
    }
    return minIndex;
};
